package ds.linklist.sorted;

/**链表的头结点*/
public class SortedLinkList {

	private Link first = null; // 这个null后来一直往后传啊传~~
	// -----------------------------
	public boolean isEmpty(){
		return (first == null);
	}
	
	public void insert(int i){

		Link newLink = new Link(i);
		if(first == null)
		{
			first = newLink;
			return;
		}
		
		Link previous = null;
		Link current = first;
		while(current!=null)
		{
			if(current.getData() >= i)
			{
				if(current == first)
				{
					newLink.next = current;
					first = newLink;
					break;
				}
				newLink.next = current;
				previous.next = newLink;
				break;
			}
			else
			{
				previous = current;
				current = current.next;
			}
		}
		if(current==null)
			previous.next = newLink;
	}
	
	public Link find(int key)
	{
		Link current = first;
		while(current!=null)
		{
			if(current.getData() == key)
				return current;
			else
				current=current.next;
		}
		return null;
	}
	
	public Link delete()
	{
		if(!isEmpty())
		{
			Link temp = first;
			first = first.next;
			return temp;
		}
		else
		{
			return null;
		}
	}
	
	public Link delete(int key)
	{		
		Link previous = null;
		Link current = first;
		
		while(current != null)
		{
			if(current.getData() == key)
			{
				Link temp = current;
				if(current == first)
					first = current.next;
				else
				{
					previous.next = current.next;
					current.next = null;
				}
				return temp;
			}
			else
			{
				previous = current;
				current = current.next;
			}
		}
		return null;
	}
	
	public void displayList()
	{
		System.out.println("(first --> last):");
		Link current = first;
		while(current!=null)
		{
			current.displayLink();
			current = current.next;
		}
	}
	
	public Link getFirst()
	{
		return first;
	}
}

class SortedLinkListApp{
	public static void main(String[] args)
	{
		SortedLinkList sll = new SortedLinkList();
		
		sll.insert(299);
		sll.insert(3);
		sll.insert(1);
		sll.insert(13);
		sll.insert(999);
		sll.insert(1735);
		
		sll.displayList();
		
		sll.delete();
		sll.delete();
		sll.delete();
		
		sll.displayList();
	}
}
